package org.hot100_6.leetcode148;

import org.algorithm.List.ListNode;

public class Solution {
    public ListNode sortList(ListNode head) {

        ListNode res = split(head, null);

        return res;
    }

    public ListNode split(ListNode start,ListNode end){
        if ( start ==null || start==end ){
            return start;
        }

        if (start.next == end){
            start.next = null;
            return start;
        }


        ListNode slow = start;
        ListNode fast = start;
        while (fast!=end){
            slow = slow.next;
            fast = fast.next;
            if (fast!=end){
                fast = fast.next;
            }
        }

        ListNode left = split(start, slow);
        ListNode right = split(slow, end);

        return sort(left, right);
    }

    public ListNode sort(ListNode left,ListNode right){
        ListNode dummy = new ListNode(-1);
        ListNode temp = dummy;

        while (left!=null && right!=null){
            if (left.val<right.val){
                temp.next = left;
                left = left.next;
            }else {
                temp.next = right;
                right = right.next;
            }

            temp = temp.next;
        }

        if (left==null){
            temp.next = right;
        }

        if (right==null){
            temp.next = left;
        }

        return dummy.next;
    }

}
